#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;

signed main() {
    freopen("in.txt", "r", stdin);
    freopen("wa.txt", "w", stdout);
    int T;
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--) {
        int n;
        string s;
        cin >> n >> s;
        int cnt = 0, ans = 0;
        vector<int> l(n + 1, 0), r(n + 1, 0);
        for (int i = 0; i < n; ++i) {
            l[i] = cnt++;
            if (s[i] == '1') cnt = 0;
        }
        cnt = 0;
        for (int i = n - 1; ~i; --i) {
            r[i] = cnt++;
            if (s[i] == '1') cnt = 0;
        }
        bool flag = 0;

        rep(i, 0, n - 1) {
            if (s[i] == '1' and s[i - 1] == '0' and s[i + 1] == '0') {
                int cl = 0, cr = 0;
                if (flag) {
                    cl = l[i] - 1, cr = r[i];
                } else
                    cl = l[i], cr = r[i];

                if (cl >= cr) {
                    s[i - 1] = '1';
                    flag = 0;
                } else {
                    s[i + 1] = '1';
                    flag = 1;
                    i = i + 1;
                }
                ans = 1;
            } else if (s[i] == '1') {
                if ((i == 0 || s[i - 1] == '1') and s[i + 1] == '0')
                    s[i + 1] = '1', i = i + 1, ans = 1;
                else if (s[i - 1] == '0' and (i == n - 1 || s[i + 1] == '1'))
                    flag = 1, s[i - 1] = '1', ans = 1;
            }
        }

        cnt = 0;
        int pos = 0;
        while (s[pos] == '0') {
            cnt++, pos++;
        }
        flag = ans;
        ans = max(ans, flag + cnt);
        rep(i, pos + 1, n - 1) {
            if (s[i] == '1') {
                ans = max(ans, flag + (cnt + 1) / 2);
                cnt = 0;
            } else
                cnt++;
        }
        if (cnt) ans = max(ans, flag + cnt);
        cout << ans << endl;
    }
    return 0;
}
/*
5
3
010
4
0100
7
0001000
5
11111
6
010101

*/